package m202401.d06;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/1/6 09:47
 */
//138. 随机链表的复制
public class Q138 {

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);

        n1.next = n2;
        n2.next = n3;

        n1.random = n1;
        n3.random = n2;

        Node node = new Q138().copyRandomList(n1);
        System.out.println();
    }

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        Map<Node, Node> map = new HashMap<>();
        Node res = new Node(-1);
        Node rp = res;
        Node p = head;
        while (p != null) {
            rp.next = new Node(p.val);
            rp.next.random = p.random;
            map.put(p, rp.next);
            p = p.next;
            rp = rp.next;
        }

        res = res.next;
        rp = res;
        while (rp != null) {
            rp.random = map.get(rp.random);
            rp = rp.next;
        }
        return res;
    }

    // Definition for a Node.
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

}
